Improved bounds for testing Dyck languages

摘要

In this paper we consider the problem of deciding membership in Dycklanguages, a fundamental family of context-free languages, comprised ofwell-balanced strings of parentheses. In this problem we are given a string oflength $n$ in the alphabet of parentheses of $m$ types and must decide if it iswell-balanced. We consider this problem in the property testing setting, whereone would like to make the decision while querying as few characters of theinput as possible. Property testing of strings for Dyck language membership for $m=1$, with anumber of queries independent of the input size $n$, was provided in [Alon,Krivelevich, Newman and Szegedy, SICOMP 2001]. Property testing of strings forDyck language membership for $m \ge 2$ was first investigated in [Parnas, Ronand Rubinfeld, RSA 2003]. They showed an upper bound and a lower bound fordistinguishing strings belonging to the language from strings that are far (interms of the Hamming distance) from the language, which are respectively (up topolylogarithmic factors) the $2/3$ power and the $1/11$ power of the input size$n$. Here we improve the power of $n$ in both bounds. For the upper bound, weintroduce a recursion technique, that together with a refinement of the methodsin the original work provides a test for any power of $n$ larger than $2/5$.For the lower bound, we introduce a new problem called Truestring Equivalence,which is easily reducible to the $2$-type Dyck language property testingproblem. For this new problem, we show a lower bound of $n$ to the power of$1/5$.